package com.sali.Tree;

/**
 给定一棵二叉搜索树和其中的一个节点 p ，找到该节点在树中的中序后继。如果节点没有中序后继，请返回 null 。

 节点 p 的后继是值比 p.val 大的节点中键值最小的节点。
 */
public class LeetCode_285 {

    boolean found = false;
    TreeNode nextNode = null;

    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
        getRes(root, p);
        return nextNode;
    }

    private void getRes(TreeNode root, TreeNode p) {
        if (  root == null ) {
            return;
        }

        getRes(root.left, p);


        if ( found ) {
            nextNode = root;
            found = false;
            return;
        }
        if ( root == p ) {
            found = true;
        }


        getRes(root.right, p);

    }

}
